/*-----------------
** description:
** Algo C(Comparison counting). This algorithm sorts R[0]~R[N-1] on the keys K[0]~K[N-1]
** by maintaining a auxiliary table COUNT[0]~COUNT[N-1] to count the number of keys
** less than a given key. After the conclusion of the algorithm, COUNT[j]+1 will sepecify
** the final position of record R[j].
**-----------------
** Auther: coanor
** Date:2009.10.11
*/

#include <stdlib.h>
#include <stdio.h>

#define ARR_SZ 32

int main()
{
  int count[ARR_SZ] = {0};
  int temp[ARR_SZ] = {0};
  int R[ARR_SZ] = {503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703,
                     503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703};
  int i,j;
  
  for (i = ARR_SZ - 1; i>0; --i) {
    for (j = i-1; j >=0; --j) {
      if (R[i] == R[j]) {
        if (j < i) {
           if (count[i] > count[j]) {
	         count[j]++;
             printf("count_j++.\n");				       
           } else if (count[i] < count[j]) {
	         count[i]++;
	         printf("count_i++.\n");				        
	       } else {
	         /* now, j < i,R[j]'s position is before R[i]'s,
	         ** we plan to make it a stable sort, so count[i] 
	         ** increased by 1.
	         */
	         count[i]++;
	         printf("Origin: R_j equals to R_i.\n");
	       }
	    }
        continue; 
      }
      if (R[i] > R[j])
         count[i]++;
      else
         count[j]++;
    }
  }

  /* print COUNT[N] content */
  for (i = 0; i < ARR_SZ; ++i) {
    if (i % 5 == 0) 
      printf ("\n");
    printf("%5d ", count[i]+1);
  }
  
  printf("\n");
    
  exit(0);
}
